1. Field of the Invention
The present invention relates to image compression and reconstruction techniques that can be used for compressing a still picture in the form of image signals obtained by a digital still camera, a digital scanner or the like, transmitting the compressed image signals to a personal computer or the like, storing the compressed image signals, and expanding or decompressing the compressed image signals to restore or reconstruct the image signals on the personal computer or the like.
2. Description of the Prior Art
To capture natural images on personal computers, digital still cameras or digital scanners using single-plate CCD image sensors, have been used. These devices each contain an image compression device and a flash memory to compress and store image signals before transferring them to the personal computer. For the compression, a non-reversible or lossy compression method like JPEG, the international standard defined by the ISO/IEC 10918-1, is normally used.
A typical image compression device utilizing a lossy compression method comprises an interpolating section, an image component correcting section and an image compressing section. The interpolating section interpolates image signals outputted from a CCD image sensor so that each pixel has all the color components, which originally contains only one value of a color component, for example, R (red), G (green) or B (blue).
A typical structure of output signals of the CCD image sensor is shown in FIG. 8, while a structure of the image signals after the interpolation is shown in FIG. 9.
The image component correcting section carries out edge enhancement, white balance adjustment and gamma correction to the interpolated image signals. The edge enhancement is performed to the image signals if necessary. The white balance adjustment is performed to adjust the image signals to the characteristic of the human visual system. The gamma correction is performed to adjust the image signals to the characteristics of a display.
The image compressing section compresses the image signals outputted from the image component correcting section. With JPEG, when the image signals are in the form of the RGB, they are converted into luminance (Y)/color difference (Cb or Cr) signals as shown in FIG. 10. After the conversion into the luminance/color difference signals, a subsampling process is carried out to decimate the color difference signals. Thereafter, the signals are divided into blocks of 8 pixels by 8 pixels, and DCT (discrete cosine transform) is performed on each block. Then, the transformed coefficients are quantized and zig-zag scanned as shown in FIG. 12. From this pattern, each set of consecutive zeros is paired with the non-zero number that follows, and Huffman coded to accomplish entropy compression. In FIG. 12, each pair of numerical values represents coordinates of a corresponding pixel.
Moreover, JPEG is provided with an xe2x80x9cescape codexe2x80x9d followed by a pair of fixed length codes in order to avoid bloating of the Huffman table.
The transformed coefficients in each block consist of one DC, coefficient and sixty-three AC coefficients. In the foregoing example, the DC coefficient represents the upper-left coefficient and the AC coefficients represent the remaining sixty-three coefficients.
The DC coefficient is encoded in the following manner:
First, calculate the difference _d_ between the current DC coefficient and the previous DC coefficient. Second, obtain a group number (ssss) and the number of additional bits corresponding to the difference _ d_ from the Huffman table shown in FIG. 11. The additional bits are used to uniquely identify the DC coefficient, e.g., the group number three has three additional bits. Then, output the Huffman coded group number and the additional bits.
On the other hand, the AC coefficients are first re-ordered, then a sequence of zeros followed by a non-zero number is replaced with a predetermined code, and then additional bits are outputted. For example, if number xe2x80x9c7xe2x80x9d follows after six zeros, a Huffman code representing xe2x80x9ca run of six zeros followed by a value of the group number 3xe2x80x9d is used. However, if there are more than 14 consecutive zeros, a code ZRL (zero run length) representing a run of 15 consecutive zeros is used. Further, a code EOB (end of block) is used if the subsequent coefficients are all zeros.
On the other hand, an image reconstruction device in the personal computer or the like receives the compressed image data produced by the image compression device and expands the data by means of reversing the compression routine. Namely, it decodes the two-dimensional Huffman codes, zig-zag positions the coefficients, dequantizes them and carries out the inverse DCT on them to reconstruct the luminance/color difference signals to reproduce the original image.
However, the foregoing conventional image signal processing technique has the following problems:
(1) It requires heavy calculations. Thus, it will take much time for compression and decompression.
As described above, in the conventional technique, the amount of data in the image signals outputted from the CCD image sensor are initially increased through interpolation. Hence, the calculation for the entropy compression will be extensive. For example, when each of the R, G and B signals of 8 bpp (bits per pel) is interpolated and converted to an RGB signal, it will become 24 bpp so that the data amount is tripled before compression. Furthermore, JPEG requires the following three complicated steps:
color space conversion, which uses a product-sum operation of decimal numbers;
DCT, which requires a large amount of calculation; and
quantization of coefficients, which requires time consuming division.
(2) Since the color difference signals are decimated before compression, the image quality will be degraded upon reconstruction.
For example, one format adopted by JPEG is 4:2:2, which decimates the color difference signals and reduces the vertical resolution by xc2xd. Therefore, image signals having 8 bpp originally, and hence 24 bpp (8,8,8) after interpolation, will be degraded to 16 bpp (8,4,4), once the 4:2:2 JPEG format is applied.
(3) Since JPEG doesn""t acknowledge the correlation between the adjacent blocks, the efficiency of compression is reduced.
In other words, JPEG encodes and compresses each 8xc3x978 block independently. Generally, the adjacent blocks in the natural image tend to have similar textures so that the coefficients after orthogonal transform, such as DCT, are likely to have similar values. Hence, JPEG is not optimizing the potential efficiency of the compression technique.
(4) Although the two-dimensional Huffman coding used in JPEG is efficient, it can not provide all the combinations of the two elements because it will cause bloating of the Huffman table. That is the reason why the escape code was introduced.
(5) The decoding process is complicated.
JPEG uses the two-dimensional Huffman table with a maximum of 16 bits, or in the case of escape coding, 28 bits. Hence, it requires the use of more than one lookup table to achieve high-speed decoding, which rendering the decoding process complicated.
Therefore, we present an improved image signal processing method that can eliminate one or more of the foregoing problems.
We further present an improved image signal processing device that can eliminate one or more of the foregoing problems.
We further present a storage medium that allows an electronic device, such as a device including a CPU (central processing unit), to carry out the foregoing improved image signal processing method.
Our improved image signal processing proceeds as follows:
First, we perform an image signal correction on each and every component of a given image, which is composed of the three primary colorsxe2x80x94red, blue and green, or the three secondary colorsxe2x80x94magenta (blue+red), yellow (red+green), and cyan (green+blue), or any tertiary colors, such as yellow+magenta, magenta+cyan, cyan+green, and green+yellow. Each pixel in an image is supposed to have _m_ bits (_m_ is a natural number) and have only one color. The image signal correction is composed of a gamma correction and a white balance adjustment. The second step is orthogonal transform, which is performed on a block basis. The third step is quantization and zig-zag scanning. And the last step is entropy coding.
What is unique about our technique is that it carries out the interpolation process after image decompression as opposed to the conventional technique that carries out the interpolation before image compression. Using this technique, we can avoid the image expansion and decimation before compression. However, without interpolation before compression, it becomes difficult to apply color space conversion that is required for efficient compression. To compensate for this, we adopted the color space conversion into the orthogonal transform.
The present invention includes a Huffman coding method that is performed on the transformed, quantized and re-ordered image signals.
With Huffman coding, a sequence of specific, consecutive codes in the subject block is represented by a predetermined, more concise code, provided that the same sequence appears in the same region of the previous block succeeded by a non-specific code. Conversely, in the Huffman decoding, the predetermined code in the subject block is replaced with a sequence of the specific codes, as long as the corresponding element in the previous block is the specific code.
The present invention provides an image signal compression and decompression device that performs the following:
1) dividing and preparing the inputted image signals into blocks.
2) orthogonal transform to each block, followed by quantization and re-ordering of elements in each block. The order of elements may be arranged to optimize compression efficiency.
3) Huffman coding that uses special codes that are used when:
i) from a certain point of the target block of an image, a specific code continues _n_ or more times (_n_ is a natural number), and
ii) from the same point of the previous block of the same image, the specific code continues no more than _n_ times.
The two-dimensional 2xc3x972 Hadamard transform can be used for the color space conversion of the image signals inputted from the single-plate CCD or the like.
As an orthogonal transform, an Hadamard transform, a Haar transform or an Hadamard-Haar transform may be applied, in which case, all the division processes can be replaced with bit shift operations to reduce the calculation amount.
In our new technique, the image signal processing method further comprises the steps of inputting and decoding the encoded image data, replacing the predetermined code in the subject block with a sequence of the specific codes, the number of which is determined by the previous block, re-positioning the elements in each block, and applying dequantization and inverse orthogonal transform to each block so as to reconstruct the original image.
The present invention further provides an image compression device comprising; quantizing means for quantizing image signals to obtain quantized data, code re-ordering means for re-ordering elements in each block of the quantized data, and encoding means for replacing a sequence of specific, consecutive codes in the subject block by a predetermined, more concise code, provided that the same sequence appears in the same region of the previous block proceeded by a nonspecific code, so as to produce compressed image data.
In our new method, an order of the elements produced by the reordering means is determined statistically so as to accomplish long runs of the specific codes.
The present invention further provides an image reconstruction device comprised of image data input means for inputting the compressed image data produced by the image compression device, and image decompressing means for replacing the predetermined code with a sequence of the consecutive specific codes, the length of which depends on the previous block.
The present invention further provides a storage medium storing a program which is readable and executable by an electronic device, the program allowing the electronic device to execute the steps of dividing image signals into a plurality of blocks, applying orthogonal transforms so as to obtain transformed data, quantizing the transformed data, re-ordering elements in each block of the quantized data, and encoding the re-ordered elements including a process of replacing a sequence of specific, consecutive codes in the subject block by a predetermined, more concise code, provided that the same sequence appears in the same region of the previous block succeeded by a non-specific code, so as to produce-compressed image data.
The present invention further provides a storage medium storing a program that is readable and executable by an electronic device. The program allows the electronic device to execute the following four steps; inputting the compressed image data produced by the image signal processing method, performing Huffman decoding for replacing the predetermined code in the subject block with a sequence of specific codes, re-positioning the elements in each block, and applying dequantization and an inverse orthogonal transform to each of the blocks so as to reconstruct the original image.